Hard disk drives are commonly used in personal computers, servers, video recorders, and many other kind of electronic devices for mass storage. Mass storage is used to store large amounts of data that is typically copied to a faster random-access memory such as a dynamic-random-access memory (DRAM) for use by a processor. While the processor's DRAM is randomly accessible, mass storage is block-accessible. An entire block of data must be read or written from the mass storage device. A RAM may allow reading and writing of individual bytes or words of 4 or 8 bytes, while a mass storage device requires that a sector or 512 bytes or more be read or written together.
Flash memory may also be used as a mass storage device in lieu of a hard disk. Flash-memory arrays are also block-accessible, but have a much faster access time than rotating media such as a hard disk. However, since flash memory chips are block-addressable rather than randomly-accessible, flash is not as easy to use for a cache as DRAM or SRAM.
FIG. 1 shows a prior-art system using flash memory. Host PC 10 generates logical sector addresses (LSA) of a 512-byte block of data to be read or written from a mass storage device. Flash memory 14 can only be erased a block at a time. Flash memory manager 12 converts LSA logical addresses from host PC 10 into physical block addresses (PBA) that identify a physical block of data in flash memory 14. Flash memory manager 12 may use re-mapping tables to perform the address translation, and may perform other flash-related functions such as wear-leveling to spread erasures over blocks in flash memory 14. An erase count may be kept for each block in flash memory 14, and the block with the lowest erase count is selected to receive new data.
FIG. 2A shows blocks and pages within an older single-level-cell (SLC) flash memory. Older flash memory chips used electrically-erasable programmable read-only memory (EEPROM) memory cells that stored one bit of data per memory cell. While an entire block had to be erased together, pages within a block could be written and over-written several times. For example, block PBA0 contains stale data in pages PG0, PG1, PG2, PG3, and could be erased as a block. However, block PBA1 has stale data in pages PG0, PG3, while currently valid data is in pages PG1, PG2.
Some older single-level-cell flash memory chips may allow over-writing of pages that have previously been written. Then stale pages PG1, PG2 could be over-written with new valid data. Since flash memory manager 12 (FIG. 1) can remap LSA's to PBA's, any data could be stored in any page in flash memory 14, regardless of its logical address LSA. Thus physical blocks in flash memory 14 could be re-filled by over-writing stale pages with new data. Blocks with all stale pages could be erased and re-used.
FIG. 2B shows blocks and pages within a newer multi-level-cell (MLC) flash memory. Newer flash memory chips use EEPROM memory cells that stored two, four, or more bits of data per memory cell. Different amounts of charge stored on the floating gates produce different current and different sensing voltages for the same memory cell. Thus a single memory cell can store multiple bits of information by assigning different voltages to different logic levels. For example, sensing voltages near Vcc are read as a logic 11, voltages near ground are a logic 00, voltages above Vcc/2 and below 0.8*Vcc are a logic 10, and voltages below Vcc/2 but above 0.2*Vcc are a logic 01.
Multi-level-cell flash memory can store a higher density than single-level cell flash for the same cell size. Thus multi-level cell flash is likely to be used more frequently for higher-density flash chips made now and in the future. However, MLC flash chips may impose additional restrictions on usage. For example, a MLC flash chip may not allow pages to be written a second time before erase. Instead, the entire block must be erased before any page can be written again. Each page may be written only once after each erase. Alternately, some writing may be allowed, such as writing a 1 bit to a 0 bit, but other writes are not allowed, such as writing a 0 bit to a 1 bit. Some MLC flash chips may be even more restrictive, only allowing pages to be written in a sequence within a block, and not allowing pages to be written out-of-order.
In FIG. 2B, valid data was written to pages PG0, PG1, PG2, PG3 in blocks PBA1, PBA2, PBA3, but later pages PG1, PG2 in block PBA1 became stale as newer data was written to a newer block in flash memory 14. Pages PG1, PG2 in block PBA1 are marked as stale, while the data in these pages is left in the pages. Since there are still valid data in pages PG0, PG3 in block PBA1, block PBA1 cannot be erased yet. Half of the space in block PBA1 contains stale data, while half contains valid data. Other blocks may have more stale pages, such as block PBA2, which has 3 stale pages. However, the one page of valid data, page PG1, prevents block PBA2 from being erased and re-used.
Since the valid data may not be replaced for a long time, if ever, blocks may contain a mix of stale and valid pages. The stale pages are wasted space in flash memory 14. When these stale pages are in blocks with valid pages, the wasted space is not recovered and remains. The amount of stale pages per block varies, but can average 50%, resulting in perhaps 50% wasted space in flash memory 14 once all blocks are used. This wasted space is undesirable, since flash memory 14 may over time eventually use all blocks, with no erased blocks available for new data.
The limitations of newer MLC flash memory may thus result in more wasted space. Stale pages that cannot be over-written are wasted space when valid data in the same block is present.
What is desired is a flash memory manager for MLC flash memory. A flash memory manager that locates and re-uses blocks with stale pages is desirable.